#ifndef _LIST_H_
#define _LIST_H_

#include "communal.h"
typedef int Rank;
#define ListNodePosi(T) ListNode<T>*

//双向链表节点类
template <typename T>
struct ListNode {
    T data;
    ListNode<T>* pred;
    ListNode<T>* succ;
    //针对header and trailer的构造器
    ListNode<T>() {}
    //默认构造器
    ListNode(T e, ListNodePosi(T) p = nullptr, ListNodePosi(T) s = nullptr)
        : data(e), pred(p), succ(s) {}

    //在当前节点前插入
    ListNodePosi(T) insertAsPred(T const& e);
    //在当前节点后插入
    ListNodePosi(T) insertAsSucc(T const& e);
};

//双向链表类
template <typename T>
class List {
   public:
    //默认构造
    List();
    //整体复制链表
    List(List<T> const& L);
    //复制L中自r起的n项，课本上的有误，这里是勘误
    List(List<T> const& L, Rank r, int n);
    //复制从p起的n项
    List(ListNodePosi(T) p, int n);

    ~List();

    //只读访问接口
    Rank size() const;
    bool empty() const;
    //重载下标运算符，低效
    T& operator[](Rank r) const;
    ListNodePosi(T) first() const;
    ListNodePosi(T) last() const;
    bool valid(ListNodePosi(T) p) const;
    int disordered() const;
    ListNodePosi(T) find(T const& e) const;
    //在无序列表的p的n个前驱中寻找e
    ListNodePosi(T) find(T const& e, int n, ListNodePosi(T) p) const;
    ListNodePosi(T) search(T const& e) const;
    //在有序列表的p的n个前驱中寻找e
    ListNodePosi(T) search(T const& e, int n, ListNodePosi(T) p) const;
    ListNodePosi(T) selectMax() const;
    //在p及其n-1个后继中选出最大者
    ListNodePosi(T) selectMax(ListNodePosi(T) p, int n) const;

    /*可写访问接口*/
    //作为首节点插入
    ListNodePosi(T) insertAsFirst(T const& e);
    //作为末节点插入
    ListNodePosi(T) insertAsLast(T const& e);
    //在p之后插入
    ListNodePosi(T) insertAfter(ListNodePosi(T) p, T const& e);
    //在p之前插入
    ListNodePosi(T) insertBefore(ListNodePosi(T) p, T const& e);
    T remove(ListNodePosi(T) p);
    void merge(List<T>& L);
    //列表整体排序
    void sort(SortMethod m = MERGE_SORT_RECURSIVELY);
    //将p后面的n个节点排序
    void sort(ListNodePosi(T) p, int n, SortMethod m = MERGE_SORT_RECURSIVELY);
    //无序列表唯一化
    int deduplicate();
    //有序列表唯一化
    int uniquify();
    //反转列表
    void reverse();

    //函数指针遍历
    void traverse(void (*)(T&));
    //函数对象遍历
    template <typename VST>
    void traverse(VST&);

   protected:
    //初始化
    void init();
    //清空整个链表
    int clear();
    //复制列表中自位置p起的n项
    void copyNodes(ListNodePosi(T), int);
    void merge(ListNodePosi(T) &, int, List<T>&, ListNodePosi(T), int);
    void mergeSort(ListNodePosi(T) &, int);
    void selectionSort(ListNodePosi(T), int);
    void insertionSort(ListNodePosi(T), int);

   private:
    int _size;
    ListNodePosi(T) header;
    ListNodePosi(T) trailer;
};  //List

//struct ListNode
template <typename T>
ListNodePosi(T) ListNode<T>::insertAsPred(T const& e) {
    ListNode<T>* x = new ListNode(e, this->pred, this);
    this->pred->succ = x;
    this->pred = x;
    return x;
}

template <typename T>
ListNodePosi(T) ListNode<T>::insertAsSucc(T const& e) {
    ListNode<T>* x = new ListNode(e, this, this->succ);
    this->succ->pred = x;
    this->succ = x;
    return x;
}

//class List public
template <typename T>
List<T>::List() {
    init();
}

template <typename T>
List<T>::List(List<T> const& L) {
    copyNodes(L.first(), L._size);
}

template <typename T>
List<T>::List(List<T> const& L, Rank r, int n) {
    ListNodePosi(T) p = first();
    while (r--)
        p = p->succ;
    copyNodes(p, n);
}

template <typename T>
List<T>::List(ListNodePosi(T) p, int n) {
    copyNodes(p, n);
}

template <typename T>
List<T>::~List() {
    clear();
    delete (header);
    delete (trailer);
}

//只读访问接口
template <typename T>
Rank List<T>::size() const {
    return _size;
}

template <typename T>
bool List<T>::empty() const {
    return _size <= 0;
}

template <typename T>
T& List<T>::operator[](Rank r) const {
    ListNodePosi(T) p = first();
    while (r-- > 0)
        p = p->succ;
    return p->data;
}

//首节点位置
template <typename T>
ListNodePosi(T) List<T>::first() const {
    return header->succ;
}

//末节点位置
template <typename T>
ListNodePosi(T) List<T>::last() const {
    return trailer->pred;
}

template <typename T>
bool List<T>::valid(ListNodePosi(T) p) const {
    return (p && (p != header) && (p != trailer));
}

template <typename T>
int List<T>::disordered() const {
    int count = 0;
    for (ListNodePosi(T) p = header->succ; p != trailer->pred; p = p->succ) {
        if (!lt(p->data, p->succ->data))
            ++count;
    }
    return count;
}

template <typename T>
ListNodePosi(T) List<T>::find(T const& e) const {
    return find(e, _size, trailer);
}

template <typename T>
ListNodePosi(T) List<T>::find(T const& e, int n, ListNodePosi(T) p) const {
    p = p->pred;
    while (n-- > 0) {
        if (e == p->data)
            return p;
        p = p->pred;
    }
    return nullptr;
}

template <typename T>
ListNodePosi(T) List<T>::search(T const& e) const {
    return search(e, _size, trailer);
}

template <typename T>
ListNodePosi(T) List<T>::search(T const& e, int n, ListNodePosi(T) p) const {
    p = p->pred;
    while (n-- >= 0) {
        if (p->data <= e)
            break;
        p = p->pred;
    }
    return p;
}

template <typename T>
ListNodePosi(T) List<T>::selectMax() const {
    selectMax(header->succ, _size);
}

template <typename T>
ListNodePosi(T) List<T>::selectMax(ListNodePosi(T) p, int n) const {
    ListNodePosi(T) max = p;
    for (ListNodePosi(T) cur = p->succ; n > 1; --n, cur = cur->succ) {
        if (!lt(cur->data, max->data))
            max = cur;
    }
    return max;
}

//可写访问接口
template <typename T>
ListNodePosi(T) List<T>::insertAsFirst(T const& e) {
    _size++;
    return header->insertAsSucc(e);
}

template <typename T>
ListNodePosi(T) List<T>::insertAsLast(T const& e) {
    _size++;
    return trailer->insertAsPred(e);
}

template <typename T>
ListNodePosi(T) List<T>::insertAfter(ListNodePosi(T) p, T const& e) {
    _size++;
    return p->insertAsSucc(e);
}

template <typename T>
ListNodePosi(T) List<T>::insertBefore(ListNodePosi(T) p, T const& e) {
    _size++;
    return p->insertAsPred(e);
}

template <typename T>
T List<T>::remove(ListNodePosi(T) p) {
    T e = p->data;
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete (p);
    _size--;
    return e;
}

//全列表归并
template <typename T>
void List<T>::merge(List<T>& L) {
    merge(first(), _size, L, L.first(), L._size);
}

template <typename T>
void List<T>::sort(SortMethod m) {
    sort(first(), _size, m);
}

template <typename T>
void List<T>::sort(ListNodePosi(T) p, int n, SortMethod m) {
    switch (m) {
        case MERGE_SORT_RECURSIVELY:
            mergeSort(p, n);
            break;
        case SELECTION_SORT:
            selectionSort(p, n);
            break;
        case INSERTION_SORT:
            insertionSort(p, n);
            break;
        default:
            mergeSort(p, n);
    }
}

template <typename T>
int List<T>::deduplicate() {
    if (_size < 2)
        return 0;
    int oldSize = _size;
    Rank r = 0;
    ListNodePosi(T) p = header->succ;
    while (p != trailer) {
        ListNodePosi(T) q = find(p->data, r, p);
        q ? remove(q) : ++r;
        p = p->succ;
    }
    return oldSize - _size;
}

template <typename T>
int List<T>::uniquify() {
    if (_size < 2)
        return 0;
    int oldSize = _size;
    ListNodePosi(T) p = first();
    ListNodePosi(T) q = p->succ;
    while (q != trailer) {
        if (p->data != q->data) {
            p = q;
            q = p->succ;
        } else {
            remove(q);
        }
    }
    return oldSize - _size;
}

template <typename T>
void List<T>::reverse() {
    //TODO
}

template <typename T>
void List<T>::traverse(void (*visit)(T&)) {
    for (ListNodePosi(T) p = header->succ; p != trailer; p = p->succ)
        visit(p->data);
    return;
}

template <typename T>
template <typename VST>
void List<T>::traverse(VST&) {
    for (ListNodePosi(T) p = header->succ; p != trailer; p = p->succ)
        visit(p->data);
    return;
}

//class List
/****protected****/
template <typename T>
void List<T>::init() {
    header = new ListNode<T>();
    trailer = new ListNode<T>();
    header->succ = trailer;
    header->pred = nullptr;
    trailer->pred = header;
    trailer->succ = nullptr;
    _size = 0;
    return;
}

template <typename T>
int List<T>::clear() {
    int oldSize = _size;
    while (_size > 0)
        remove(header->succ);
    return oldSize;
}

template <typename T>
void List<T>::copyNodes(ListNodePosi(T) p, int n) {
    init();
    while (n--) {
        insertAsLast(p->data);
        p = p->succ;
    }
    return;
}

template <typename T>
void List<T>::merge(ListNodePosi(T) & p, int n, List<T>& L, ListNodePosi(T) q, int m) {
    ListNodePosi(T) pp = p->pred;
    while (m > 0) {
        if ((n > 0) && (p->data <= q->data)) {
            if (q == (p = p->succ))
                break;
            --n;
        } else {
            insertBefore(p, L.remove((q = q->succ)->pred));
            --m;
        }
    }
    p = pp->succ;
}

template <typename T>
void List<T>::mergeSort(ListNodePosi(T) & p, int n) {
    if (n < 2)
        return;
    int m = n / 2;
    ListNodePosi(T) q = p;
    for (int i = 0; i > m; ++i)
        q = q->succ;
    mergeSort(p, m);
    mergeSort(q, n - m);
    merge(p, m, *this, q, n - m);
}

template <typename T>
void List<T>::selectionSort(ListNodePosi(T) p, int n) {
    ListNodePosi(T) head = p->pred;
    ListNodePosi(T) tail = p;
    for (int i = 0; i < n; ++i)
        tail = tail->succ;
    while (n > 1) {
        ListNodePosi(T) max = selectMax(head->succ, n);
        insertBefore(tail, max);
        remove(max);
        --n;
    }
    return;
}

template <typename T>
void List<T>::insertionSort(ListNodePosi(T) p, int n) {
    for (int r = 0; r < n; ++r) {
        //从p开始向前r找到合适位置插入
        insertAfter(search(p->data, r, p), p->data);
        p = p->succ;
        remove(p->pred);
    }
}

#endif